Networks are used to transfer voice, video and data between various network devices. Network devices such as switches are located within networks to direct the transfer of network traffic between various devices. Network traffic is typically bursty in nature. In order to compensate for network traffic bursts, memory queues are incorporated into network devices. These allow the device to temporarily store traffic when the incoming rate is higher than an available outgoing rate. When more than one queue has traffic and each queue is contending for the same bandwidth, some of the traffic is required to wait in the queues and some mechanism is needed to determine how traffic contention is resolved.
In order to resolve contention and provide a Quality of Service guarantee or some method of fair contention resolution to traffic, queue management algorithms must be implemented in the network devices. In one algorithm referred to as “priority queuing”, contending queues are assigned different priorities and traffic is forwarded from the queues in strict priority order. For example, referring to FIG. 1, four queues Q1, Q2, Q3 and Q4 (designated 1–4 respectively) hold packetised traffic that is to be forwarded on link (20). The link (20) has a finite bandwidth RL that must be shared by the traffic. To resolve the contention, the queues are prioritized and packets from the queues are forwarded to the link (20) in strict priority order under the control of a queue manager (10), such as a switch. While priority queuing works well when there is little contention, where there is contention, traffic from higher priority queues is forwarded at the expense of traffic from lower priority queues. In this situation, lower priority queues might be totally blocked since the priority mechanism allows the high priority queue to transmit traffic any time when the queue is not empty.
One algorithm that attempts to resolve issues surrounding contention management without the above problems is “Weighted Fair Queuing” (WFQ). Contending queues are assigned weights and packets are forwarded from queues in proportion to the weights assigned to each queue. For example, referring again to FIG. 1, the four queues are assigned a weight that represents the amount of bandwidth that is reserved for that queue. If the total available bandwidth of the link were 100 bytes per second, then with queue weights assigned as 20%, 25%, 15% and 40% to Q1, Q2, Q3 and Q4 respectively, Q1 would be allocated 20 bytes per second on the link, Q2 would be allocated 25 bytes per second, Q3 15 bytes per second and Q4 40 bytes per second. By using a WFQ mechanism the rate of each queue is guaranteed and queues cannot starve each other. In one implementation of the weighted fair queue algorithm, a linear array is defined. Each array element represents a transmission time on the outgoing link. Queues are scheduled by linking them to one of the elements in the array, the order of transmission being determined by the order of the queues in the array. Once a transmission is made from a queue according to the schedule, the position of the queue within the array is recalculated. The recalculation schedules the queue further along the array, the exact position being calculated in dependence on the queue's assigned weight.
Whilst the basic Weighted Fair Queue algorithm works well for preventing starvation that occurs in priority queuing and establishes a maximum flow rate for each queue, link bandwidth is often wasted because the percentage of link bandwidth reserved for a particular queue is reserved whether or not there are packets waiting. There is no apparent way of distributing excess bandwidth between other queues because queues do not have priority assigned relative to one another.
The number of weights supported is important in WFQ system—it determines the ratio between the highest bandwidth (BW) supported to the lowest bandwidth supported. A WFQ system with a large number of weights supports a large variety of different bandwidths. The number of weights also determines the granularity, granularity being the proportion of bandwidth each weight represents:   Granularity  =                    {                  BW_of          ⁢          _weight          ⁢          _N                }            ⁢                          ⁢              {                  BW_of          ⁢          _weight          ⁢          _          ⁢                      (                          N              ⁢                                                          ⁢              1                        )                          }                    BW_of      ⁢      _weight      ⁢      _N      
Obviously, a system is more efficient if the granularity is fine because a weight that is assigned to a queue is likely to represent a bandwidth closer to that required. Where granularity is coarse, each increase in weight is likely to correspond to a large increase in bandwidth and therefore it is unlikely a close match to the bandwidth requirement can be found. The number of weights that can be used and the granularity between the weights is dependent on the size of the array. Obviously, the larger the array the more complex the processing of the WFQ algorithm becomes and the more memory or logic elements are needed to support the system. Thus, there exists a trade-off between the number of weights and their respective granularity and the processing speed of the system.
Implementing traffic management in high-speed network nodes like routers or switches requires high-speed hardware or software. The WFQ algorithm must complete calculations within a cell time (in high speed lines of speeds of 622 mb/s or above this is less then 1 μs). However, the complexity of algorithms such as WFQ inhibits their use in high-speed switches which must select a cell for transmission every few microseconds (or less). In addition, it is difficult to scale the algorithm to tens of thousands of connections multiplexed onto a single link without increasing the selection time for each cell.
With the advent of high speed links and small cell sizes, modem networking devices, such as switches, require efficient hardware and corresponding algorithms to process cell arrivals in an extremely short space of time. However, at present there exists a trade-off between cell selection time and the scalability such algorithms.
It may also be desirable for a queue management algorithm to be work conserving, i.e. where there is waiting traffic in queues, scheduling calculations should be completed within a cell time in order to prevent wasted transmission times on the link. A large number of queues should also be supported—this is essential in a per-VC or a per-flow node. If implemented in a logic gate system such as ASIC or FPGA, a low number of logic gates should be used to limit cost and complexity and increase processing speed Furthermore, in weighted algorithms such as weighted fair queuing, a large number of weights should be supported in order to support incoming links with varying bandwidths.
Scheduling methods of this type is particularly relevant to ATM (Asynchronous Transfer Mode) networks. However, most types of network, such as IP, now offer some kind of Quality of Service (QoS) to which such scheduling methods are relevant. ATM supports several classes of services: CBR (Constant Bit Rate); VBR (Variable Bit Rate); ABR (Available Bit Rate); GFR (Guaranteed Frame Rate) and UBR (Unspecified Bit Rate). Traffic in ATM is divided into fixed size cells. Traffic may be sensitive to delay and delay variation. Connections may require traffic below an agreed rate to be guaranteed to be delivered. Connections normally have some form of agreed maximum transmission rate. However this is not always the case and traffic may in these cases be delivered on a best-effort basis.
U.S. Pat. No. 5,831,971 issued to Lucent Technologies, Inc. discloses a traffic management system based on a combination of leaky bucket traffic shaping and weighted fair queuing collision arbitration. Virtual finishing times based on the time a cell transmission would have completed under idealized fair queuing is used to select cells awaiting transmission. A selected cell is only transmitted is the leaky bucket shaper determines that the cell conforms to the agreed traffic contract. Non-conforming cells are re-assigned a new virtual finishing time and left in a queue for transmission.
U.S. Pat. No. 5,864,540 issued to AT&T Corp./CSI Zeinet and U.S. Pat. No. 6,011,775 issued to AT&T Corp. disclose traffic shaping methods for packet-switched networks in which leaky bucket traffic shaping is combined with weighted round robin scheduling. Incoming traffic is queued in separate queues which are served on a round robin basis in dependence on a priority calculated from the traffic's bandwidth. Cells selected from the queues are only transmitted if the transmission satisfies the leaky bucket approximation of the agreed traffic contract.